package algorithm;

/**
 * 八皇后(规则：不可出现在同一行，同一列，同一斜线)
 * 92种解决方案
 * 回溯算法
 */
public class Queue8 {
    //共有多少个皇后
    int max = 8;
    //保存皇后放置位置的结果,如{0,4,7,5,2,6,1,3}
    int[] array = new int[max];

    static int count = 0;
    static int judgeCount = 0;

    public static void main(String[] args) {
        long startTime = System.currentTimeMillis();
        Queue8 queue8 = new Queue8();
        queue8.check(0);
        System.out.printf("共有%d种解法",count);
        System.out.println();
        System.out.printf("共判断冲突%d次",judgeCount);
        System.out.println();
        System.out.println("pay:"+(System.currentTimeMillis()-startTime));
    }

    /**
     * 放置第n个皇后
     * check每次递归时，在for中会有回溯
     * @param n
     */
    public void check(Integer n) {
        if (n == max) { //8皇后全了
            print();
            return;
        }
        //依次放入皇后，并判断是否冲突
        for(int i=0;i<max;i++){
            //先把当前这个皇后n，放到该行的第1列（假设行为）
            array[n] = i;
            //判断当放置第n个皇后到i列时，是否冲突
            if(judge(n)){ //不冲突
                //接着放n=1皇后，即开始递归
                check(n+1);
            }
            //如果冲突，就继续执行array[n]=i;即将第n个皇后，放置在本行得后移一个位置（i++）
        }
    }

    /**
     * 查看当我们放置第n个皇后，就去检测该皇后是否和前面已经摆放的皇后冲突
     * @param n 第几个皇后
     * @return
     */
    public boolean judge(int n) {
        judgeCount++;
        for( int i=0; i<n; i++ ) {
            /**
             * array[i] == array[n]：
             * 判断第n个皇后是否和前面的n-1个皇后在同一列（i表示行，所以无需关注）
             *
             * Math.abs(n-i) == Math.abs(array[n]-array[i])：
             * 判断第n个皇后是否和第I个皇后在同一斜线
             *
             * n=1 放置第2列 array[1] = 1
             * i = 0
             *
             * Math.abs(1-0) = 1
             * Math.abs(array[n]-array[i]) = Mach.abs(1-0) = 1
             */
            if (array[i] == array[n] || Math.abs(n-i) == Math.abs(array[n]-array[i])){
                return false;
            }
        }
        return true;
    }


    private void print() {
        count++;
        for(int i = 0; i < array.length;i++){
            System.out.print(array[i]+" ");
        }
        System.out.println();
    }
}
